package 优先算法.递归_搜索与回溯.二叉树深度搜索.二叉树的所有路径;

import java.util.ArrayList;
import java.util.List;

/**
 *https://leetcode.cn/problems/binary-tree-paths/
 */
public class Main {
    public static void main(String[] args) {
        Solution so = new Solution();
        Solution.TreeNode root = new Solution.TreeNode(1);
        root.left = new Solution.TreeNode(2);
        root.right = new Solution.TreeNode(3);
//        root.left.left = new Solution.TreeNode(0);
        root.left.right = new Solution.TreeNode(5);

        List<String> rel = so.binaryTreePaths(root);
        System.out.println(rel);
//        printTree(rel); // 打印剪枝后的树
    }
    private static void printTree(Solution.TreeNode node) {
        if (node == null) return;
        System.out.print(node.val + " ");
        printTree(node.left);
        printTree(node.right);
    }
}
class Solution {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    static List<String> ret ;
    public List<String> binaryTreePaths(TreeNode root) {
        ret = new ArrayList<>();
        StringBuffer path = new StringBuffer();
        //函数头
        dfs(root,path);
        return ret;
    }
    public static void dfs(TreeNode root, StringBuffer path){
        //出口
        if(root == null) return;
        if(root.left == null && root.right == null){
            path.append(root.val);
            ret.add(String.valueOf(path));
            return;
        }
        path.append(root.val+"->");
        dfs(root.left,new StringBuffer(path));
        dfs(root.right,new StringBuffer(path));
    }
    /*List<String> ret;
    public List<String> binaryTreePaths(TreeNode root) {
        ret = new ArrayList<>();
        dfs(root,new StringBuffer());
        return ret;
    }
    void dfs(TreeNode root,StringBuffer _path){
        StringBuffer path = new StringBuffer(_path);
        path.append(Integer.toString(root.val));
        if(root.left == null && root.right == null){
            ret.add(path.toString());
            return;
        }
        path.append("->");
        if(root.left != null) dfs(root.left,path);
        if(root.right != null) dfs(root.right,path);
    }*/
}
